Apprentissage par différences temporelles (Temporal-Difference - TD)¶
5. Méthode Sarsa : Contrôle de type On-Policy¶
Nous allons maintenant nous intéresser à l'utilisation des méthodes par différences temporelles dans le but de construire des stratégies optimales. Comme d'habitude, nous allons suivre les idées proposées par les méthodes d'itérations des stratégies généralisées (GPI), en utilisant les méthodes TD pour l'évaluation et la prédiction. Comme pour les méthodes de Monte-Carlo nous allons être confronté au problème de balance entre l'exploitation et l'exploration. Ici nous nous intéressons à une méthode de type On-Policy.
5.1. Présentation de la méthode Sarsa
La première étape est d'apprendre les fonctions des valeurs d'actions plutôt que les fonctions des valeurs d'états. Pour une méthode de type On-Policy, l'objectif est donc d'estimer la valeur des paires d'état-action de l'environnement $q_\pi(s,a)$, pour une stratégie $\pi$ et pour tous les états $s$ et les actions $a$ de l'environnement. Cela peut être réalisé en suivant le même procédé que nous avons pris lors de la prédiction pour apprendre $V_\pi$.
Précédemment, nous considérions les transitions d'état à état dans le but d'apprendre la valeur des états. Maintenant, nous allons considérer les transitions de paires d'état-action à paire d'état-action dans le but d'apprendre les valeurs des paires d'état-action. On peut montrer que la convergence est assurée pour l'équation récurrente suivante:
Cette mise à jour est réalisée après chaque transition depuis un état $S_t$. Si $S_{t+1}$ est un état terminal, alors $Q(S_{t+1},A_{t+1})$ est défini comme valant zéro. L'équation Récurrentes précédentes utilisent donc un ensemble de cinq éléments $\left( {{S_t},{A_t},{R_{t + 1}},{S_{t + 1}},{A_{t + 1}}} \right)$ lors des transitions d'une paire d'état-action vers la prochaine. Cet ensemble de cinq éléments induit donc le nom de SARSA à l'algorithme.
Il est très facile d'établir un algorithme de contrôle basé sur l'équation Sarsa. Il suffit d'estimer en continu $q_\pi$ pour la stratégie $\pi$, et de modifier cette stratégie de manière optimale par rapport à $q_\pi$.
La convergence de l'algorithme Sarsa dépend de la manière dont la stratégie est liée à la fonction des valeurs d'action $Q$. On peut par exemple utiliser une stratégie de type $\varepsilon$-greedy ou de type $\varepsilon$-soft. La méthode Sarsa converge avec une probabilité de 1 vers une stratégie optimale et une fonction des valeurs d'action optimale tant que toutes les paires d'état-action sont visitées une infinité de fois et que la stratégie converge vers une stratégie optimale (cela peut se faire par exemple avec une stratégie de type $\varepsilon$-greedy en imposant $\varepsilon=1/t$
Algorithme
